%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Algorithmic Graph Theory
%% http://code.google.com/p/graphbook/
%%
%% Copyright (C) 2009--2013 Minh Van Nguyen <mvngu.name@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{algorithmic}[1]
%% input and output
\Require A weighted connected graph $G = (V,E)$ with weight function
  $w$.  All the edge weights of $G$ are distinct.
\Ensure A minimum spanning tree $T$ of $G$.
%%
%% algorithm body
\State $n \gets |V|$\label{alg:Boruvka:get_graph_order}
\State $T \gets \overline{K}_n$\label{alg:Boruvka:spanning_forest}
\While{$|E(T)| < n - 1$\label{alg:Boruvka:while_loop_start}}
  \For{\rm each component $T'$ of $T$\label{alg:Boruvka:for_loop}}
    \State $e' \gets$ edge of minimum weight that leaves $T'$
    \State $E(T) \gets E(T) \cup e'$\label{alg:Boruvka:while_loop_end}
  \EndFor
\EndWhile
\State \Return $T$
\end{algorithmic}
